package Graph.Medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC1466 {
    int reorderNum = 0, n;
    boolean[] visited;
    byte[][] matrix; // 邻接矩阵
    List<LinkedList<int[]>> list; // 邻接矩阵；这个邻接矩阵存储了所有与该顶点u相连的路径，不论是否从u出发

    // 基于邻接矩阵的解法，会超出内存限制
    public int minReorderMatrix(int n, int[][] connections) {
        matrix = new byte[n][n];
        this.n = n;
        visited = new boolean[n];
        for (int[] path : connections) {
            matrix[path[0]][path[1]] = 1;
            matrix[path[1]][path[0]] = -1; // 反向路线
        }

        visited[0] = true;
        dfsMatrix(0);
        return n - 1 - reorderNum; // dfs过程统计的是0出发到任意点的情况下需要反转的路线数，实际上我们反转的是dfs过程中没有反转的那些路线
    }

    private void dfsMatrix(int u) {
        for (int v = 0; v < n; v++) {
            if (matrix[u][v] != 0 && !visited[v]) {
                if (matrix[u][v] != 1) {
                    reorderNum++;
                    matrix[u][v] = (byte) -matrix[u][v];
                    matrix[v][u] = (byte) -matrix[v][u];
                }
                visited[v] = true;
                dfsMatrix(v);
            }
        }
    }

    public int minReorder(int n, int[][] connections) {
        this.n = n;
        list = new ArrayList<>(n);
        visited = new boolean[n];
        for (int i = 0; i < n; i++) list.add(new LinkedList<>());
        for (int[] path : connections) {
            list.get(path[0]).add(path);
            list.get(path[1]).add(path);
        }

        visited[0] = true;
        dfsList(0);
        return n - 1 - reorderNum;
    }

    private void dfsList(int u) {
        List<int[]> adjListForThisElem = list.get(u);
        for (int[] path : adjListForThisElem) {
            int v = path[0] == u ? path[1] : path[0];
            if (!visited[v]) {
                if (path[0] == v) { // 需要反转
                    path[0] = u;
                    path[1] = v;
                    reorderNum++;
                }
                visited[v] = true;
                dfsList(v);
            }
        }
    }

    public static void main(String[] args) {
        LC1466 solution = new LC1466();
        int[][] connections = new int[][]{{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
        System.out.println(solution.minReorder(6, connections));
    }
}
